

		TRAMVAI SI METROU
	       --------------------

	Intr-un oras linistit din America, municipalitatea a promis alegatorilor sa
construiasca linii de tramvai pe strazile orasului. Cetatenii care nu au autoturisme
sunt interesati ca strada lor sa dispuna de tramvai si cer o despagubire din partea
primariei in cazul ca pe strada lor nu se introduce o astfel de linie. Cetatenii care
au autoturisme sunt mai interesati de pastrarea linistii pe strada lor si cer o des-
pagubire din partea primariei in cazul in care pe strada lor va trece tramvaiul. Din
fondurile CIMAU (Comisia Internationala pentru Modernizarea Asezarilor Urbane, cu
sediul in Romania), municipalitatea are posibilitea sa construiasca (fara cheltuieli)
proprii legaturi directe subterane intre oricare 2 puncte ale orasului cu conditia ca
nici o linie de metrou construita sa coincida cu o strada.
	Cunoscandu-se numarul de puncte (intersectii) si perechile de puncte intre care
exista strada, despagubirea ceruta de fiecare dintre cele doua categorii de cetateni
pentru fiecare strada si stiind ca orice punct al orasului este capatul a cel putin o
strada, sa se stabileasca strazile pe care municipalitatea trebuie sa introduca o linie
de tramvai si punctele intre care trebuie sa se construiasca linii de metrou, astfel incat
din orice punct sa se poata ajunge (cu ajutorul mijloacelor de transport in comun) in
oricealt punct al orasului, si costul total (rezultat din plata despagubirilor) sa fie
minim. Pentru doua solutii cu acelasi cost total se va alege o solutie cu un numar minim
de linii de metrou construite.

	Din fisierul TRAMVAI.IN se citesc:
- de pe prima linie numarul n de intersectii si numarul s de strazi existente intre aceste
intersectii, cele 2 valori fiind despartite printr-un spatiu (n<=100;s<=5000).
	considerand intersectiile numerotate de la 1 la n, se citesc de pe urmatoarele s linii
ale fisierului cate 4 numere reprezentand:
- cele 2 numere ale intersectiilor din capete, suma ceruta de cetatenii care nu vor tramvai
pe strada respectiva, si despagubirea ceruta de cei care vor tramvai (numere naturale de cel
mult 4 cifre fiecare)

	In fisierul TRAMVAI.OUT se afiseaza:
- costul total al despagubirilor, c, pe prima linie
- nr. de liniee de tramvai construite, t pe a doua linie;
- t perechi de numere reprezentand strazi pe care se introduce linie tramvai, pe urmatoarele
t linii;
- numarul m de linii de metrou, pe urmatoarea linie;
- m perechi de numere reprezentand intersectile pe care se construieste linie de metrou, pe
urmatoarele m linii

	Daca exista mai multe solutii, se va scrie in fisier una singura. daca nu exista solutii,
se va afisa pe ecran un mesaj explicativ.

EXEMPLU:
TRAMVAI.IN			TRAMVAI.OUT
5 8				31
1 2 10 4			3
2 3 5 8				1 5
3 4 7 2				2 3
1 4 5 10			2 4
1 4 7 2				1
2 5 5 3				3 5
5 1 3 8
4 5 12 7